Sieve of Eratosthenes Algorithm
The Sieve of Eratosthenes is an ancient algorithm used for finding all prime numbers up to a given limit. It is named after the Greek mathematician Eratosthenes, who was the chief librarian at the Library of Alexandria around 200 BC. The algorithm works by iteratively marking the multiples of each prime number, starting from the smallest prime (2), and proceeding in increasing order. By crossing out the multiples of each prime, the remaining unmarked numbers are identified as prime numbers.
The algorithm begins by creating a list of numbers from 2 to the desired limit (inclusive). The first number (2) is considered prime, and all of its multiples in the list are marked as composite (non-prime). The next unmarked number (3) is then considered prime, and its multiples are similarly marked as composite. This process is repeated for each subsequent unmarked number until the end of the list is reached or the square of the current prime exceeds the limit. At the end of the process, all unmarked numbers in the list are considered prime numbers. The Sieve of Eratosthenes is an efficient and straightforward method for finding prime numbers, with a time complexity of O(n log log n) for finding all primes up to the integer n.
/*
Petar 'PetarV' Velickovic
Algorithm: Sieve of Eratosthenes
*/
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <complex>
#define MAX_N 1000001
using namespace std;
typedef long long lld;
vector<int> primes;
bool mark[MAX_N];
//Algoritam koji izdvaja sve proste brojeve do broja B
//Slozenost: O(N log log N)
inline void sieve(int B)
{
if (B > 1) primes.push_back(2);
for (int i=3;i<=B;i+=2)
{
if (!mark[i])
{
mark[i]=true;
primes.push_back(i);
if (i<=sqrt(B)+1) for (int j=i*i;j<=B;j+=i) mark[j]=true;
}
}
}
int main()
{
sieve(30);
for (int i=0;i<primes.size();i++) printf("%d\n",primes[i]);
return 0;
}
